Mirror descent [37] is becoming increasingly popular in a variety of settings in optimization and machine learning. One reason for its success is the fact that mirror descent can be adapted to fit the geometry ofthe optimization problem athand bychoosing asuitable strictly convexpotential function,theso-calledmirrormap.

Phase retrieval, the problem of reconstructing a signal from the (squared) magnitude of its Fourier (or any linear) transform, arises in many fields of science and engineering. Such a task is naturally involved in applications such as crystallography (Millane, 1990) and diffraction imaging (Bunk et al., 2007), where optical sensors are able to measure the intensity, but not the phase of a light wave. Due to the loss of phase information, the one-dimensional Fourier phase retrieval problem is ill-posed in general. Common approaches to overcome this ill-posedness include using prior information such as non-negativity, sparsity and the signal's magnitude (Fienup, 1982; Jaganathan et al., 2016), or introducing redundancy into the measurements by oversampling random Gaussian measurements or coded diffraction patterns (Candès et al., 2015; Chen and Candès, 2015). In many applications, the underlying signal is naturally sparse (Jaganathan et al., 2016). A wide range of algorithms has been devised for phase retrieval with a sparse signal, including alternating minimization (SparseAltMinPhase) (Netrapalli et al., 2015), non-convex optimization based approaches such as thresholded Wirtinger flow (TWF) (Cai et al., 2016), sparse truncated amplitude flow (SPARTA) (Wang et al., 2018), compressive reweighted amplitude flow (CRAF) (Zhang et al., 2018) and sparse Wirtinger flow (SWF) (Yuan et al., 2019), and convex relaxation methods such as compressive phase retrieval via lifting (CPRL) (Ohlsson et al., 2012) and SparsePhaseMax (Hand and Voroninski, 2016). Other approaches to sparse phase retrieval include the greedy algorithm GESPAR (Schechtman et al., 2014), an algorithm based on generalized

The problem of phase retrieval has been intriguing researchers for decades due to its appearance in a wide range of applications. The task of a phase retrieval algorithm is typically to recover a signal from linear phase-less measurements. In this paper, we approach the problem by proposing a hybrid model-based data-driven deep architecture, referred to as the Unfolded Phase Retrieval (UPR), that shows potential in improving the performance of the state-of-the-art phase retrieval algorithms. Specifically, the proposed method benefits from versatility and interpretability of well established model-based algorithms, while simultaneously benefiting from the expressive power of deep neural networks. Our numerical results illustrate the effectiveness of such hybrid deep architectures and showcase the untapped potential of data-aided methodologies to enhance the existing phase retrieval algorithms.

Over-the-air computation (AirComp) shows great promise to support fast data fusion in Internet-of-Things (IoT) networks. AirComp typically computes desired functions of distributed sensing data by exploiting superposed data transmission in multiple access channels. To overcome its reliance on channel station information (CSI), this work proposes a novel blind over-the-air computation (BlairComp) without requiring CSI access, particularly for low complexity and low latency IoT networks. To solve the resulting non-convex optimization problem without the initialization dependency exhibited by the solutions of a number of recently proposed efficient algorithms, we develop a Wirtinger flow solution to the BlairComp problem based on random initialization. To analyze the resulting efficiency, we prove its statistical optimality and global convergence guarantee. Specifically, in the first stage of the algorithm, the iteration of randomly initialized Wirtinger flow given sufficient data samples can enter a local region that enjoys strong convexity and strong smoothness within a few iterations. We also prove the estimation error of BlairComp in the local region to be sufficiently small. We show that, at the second stage of the algorithm, its estimation error decays exponentially at a linear convergence rate.

We consider the robust phase retrieval problem of recovering the unknown signal from the magnitude-only measurements, where the measurements can be contaminated by both sparse arbitrary corruption and bounded random noise. We propose a new nonconvex algorithm for robust phase retrieval, namely Robust Wirtinger Flow to jointly estimate the unknown signal and the sparse corruption. We show that our proposed algorithm is guaranteed to converge linearly to the unknown true signal up to a minimax optimal statistical precision in such a challenging setting. Compared with existing robust phase retrieval methods, we achieve an optimal sample complexity of $O(n)$ in both noisy and noise-free settings. Thorough experiments on both synthetic and real datasets corroborate our theory.

We study the phase retrieval problem, which solves quadratic system of equations, i.e., recovers a vector $\boldsymbol{x}\in \mathbb{R}^n$ from its magnitude measurements $y_i=|\langle \boldsymbol{a}_i, \boldsymbol{x}\rangle|, i=1,..., m$. We develop a gradient-like algorithm (referred to as RWF representing reshaped Wirtinger flow) by minimizing a nonconvex nonsmooth loss function. In comparison with existing nonconvex Wirtinger flow (WF) algorithm \cite{candes2015phase}, although the loss function becomes nonsmooth, it involves only the second power of variable and hence reduces the complexity. We show that for random Gaussian measurements, RWF enjoys geometric convergence to a global optimal point as long as the number $m$ of measurements is on the order of $n$, the dimension of the unknown $\boldsymbol{x}$. This improves the sample complexity of WF, and achieves the same sample complexity as truncated Wirtinger flow (TWF) \cite{chen2015solving}, but without truncation in gradient loop. Furthermore, RWF costs less computationally than WF, and runs faster numerically than both WF and TWF. We further develop the incremental (stochastic) reshaped Wirtinger flow (IRWF) and show that IRWF converges linearly to the true signal. We further establish performance guarantee of an existing Kaczmarz method for the phase retrieval problem based on its connection to IRWF. We also empirically demonstrate that IRWF outperforms existing ITWF algorithm (stochastic version of TWF) as well as other batch algorithms.

This paper considers the noisy sparse phase retrieval problem: recovering a sparse signal $x \in \mathbb{R}^p$ from noisy quadratic measurements $y_j = (a_j' x )^2 + \epsilon_j$, $j=1, \ldots, m$, with independent sub-exponential noise $\epsilon_j$. The goals are to understand the effect of the sparsity of $x$ on the estimation precision and to construct a computationally feasible estimator to achieve the optimal rates. Inspired by the Wirtinger Flow [12] proposed for noiseless and non-sparse phase retrieval, a novel thresholded gradient descent algorithm is proposed and it is shown to adaptively achieve the minimax optimal rates of convergence over a wide range of sparsity levels when the $a_j$'s are independent standard Gaussian random vectors, provided that the sample size is sufficiently large compared to the sparsity of $x$.